/**
 * https://leetcode-cn.com/problems/majority-element/
 * 多数元素
 * @param nums 
 */
const majorityElement = (nums: number[]): number => {
    // 1. 排序
    nums.sort((a, b) => a - b);

    // 2. 返回中间元素
    return nums[nums.length >> 1]
};


const majorityElement2 = (nums: number[]): number => {
    const map: Record<number, number> = {},
        len = nums.length,
        half = len >> 1;

    let ans = -1
    // 遍历元素
    for (let i = 0; i < len; i++) {
        let curr = nums[i];

        // 对应的项数目加1 
        map[curr] = map[curr] ?? 0
        const t = ++map[curr]

        // 某个数加起来超过了一半
        if (t > half) {
            ans = curr;
            break;
        }
    }
    return ans
};